package com.cheung.leetcode.arr;

import java.util.Arrays;

public class LC977 {

    public static int[] sortedSquares(int[] nums) {
        // 排序,此处使用插入排序
        nums[0] *= nums[0];
        for (int i = 1; i < nums.length; i++) {
            int d = nums[i] * nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > d) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = d;
        }

        return nums;
    }

    public static int[] sortedSquaresV2(int[] nums) {
        int[] res = new int[nums.length];
        int i = 0;
        int index = nums.length - 1;
        int j = nums.length - 1;
        while (i <= j) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                res[index--] = nums[i] * nums[i];
                i++;
            } else {
                res[index--] = nums[j] * nums[j];
                j--;
            }
        }
        return res;
    }


    public static void main(String[] args) {
        int[] nums = {-4, -1, 0, 3, 10};
        System.out.println(Arrays.toString(sortedSquaresV2(nums)));
    }
}
